

/**
 *  [0,0,1,0,1,1,0], // 1
 *  [1,0,0,1,0,0,0], // 4
 *  [0,1,0,0,0,0,1], // 5
 */

/**
 *
 *  算法实现:
 *  1. 从矩阵中先选一行
 *  2. 根据定义 计算出剩余的矩阵, 计为K
 *  3. 如果:
 *     a. K为空矩阵,且之前的一行都是1， 那么求解结束.
 *     b. 如果K不为空，继续求解,跳到步骤1.
 *     c. K为空矩阵,之前的一行中有0,跳到步骤4
 *  4. 说明之前的选中有误，回溯到之前的一个矩阵.
 *     a. 到步骤1,选择矩阵下一行,继续求解.
 *     b. 没有矩阵可以选择/回溯,说明问题无解,到步骤6
 *  5. 求解结束,输出解的结果
 *  6. 求解结束,输出无解消息
 */


let map = [
    [0,0,1,0,1,1,0], // 1
    [1,0,0,1,0,0,1],
    [0,1,1,0,0,1,0],
    [1,0,0,1,0,0,0], // 4
    [0,1,0,0,0,0,1], // 5
    [0,0,0,1,1,0,1],
];

class DLXLink{
    constructor(rowIdx,colIdx,value){
        this.left = null;
        this.right = null;
        this.up = null;
        this.down = null;

        this.value = (value === undefined)?-1:value;
        this.rowIdx = rowIdx;
        this.colIdx = colIdx;
    }

    toJSON(){
        return `rowIdx:${this.rowIdx},colIdx:${this.colIdx}`;
    }
}

function builFramMap() {
    let rowCount = map.length;
    let colCount = map[0].length;

    let cRows = [];
    let head = new DLXLink(0,0);
    let c1 = new DLXLink(0,1);
    let c2 = new DLXLink(0,2);
    let c3 = new DLXLink(0,3);
    let c4 = new DLXLink(0,4);
    let c5 = new DLXLink(0,5);
    let c6 = new DLXLink(0,6);
    let c7 = new DLXLink(0,7);
    cRows.push(head,c1,c2,c3,c4,c5,c6,c7);

    for(let k = 0; k < cRows.length;++k){
        let cur = cRows[k];
        cur.right = (k + 1 >= cRows.length )?cRows[0]:cRows[k+1];
        cur.left = (k - 1 < 0)?cRows[cRows.length-1]:cRows[k - 1];
    }

    let links = [];
    for(let i = 0; i < rowCount; ++i){
        links[i] = [];
        for(let j = 0; j < colCount; ++j){
            if(map[i][j] > 0){
                let node = new DLXLink(i + 1,j + 1,map[i][j]);
                links[i].push(node);
            }
        }
    }

    // 定义水平方向关系
    for(let i = 0,len = links.length; i < len; ++i){
        let row = links[i];
        if(row.length > 0){
            for(let k = 0; k < row.length;++k){
                let cur = row[k];
                cur.right = (k + 1 >= row.length )?row[0]:row[k+1];
                cur.left = (k - 1 < 0)?row[row.length-1]:row[k - 1];
            }
        }
    }

    /**
     * 这里要小心
     * @param rowIdx
     * @param colIdx
     * @returns {null}
     */
    function getNode(rowIdx,colIdx) {
        let row = links[rowIdx];
        for(let i = 0,len = row.length; i < len; ++i){
            let node = row[i];
            if(node.rowIdx === rowIdx + 1 && node.colIdx === colIdx + 1){
                return node;
            }
        }
        return  null;
    }

    //  定义垂直方向关系
    for(let k = 1;k < cRows.length;++k){
        let cur = cRows[k];
        let tmpArr = [cur];
        for(let t = 0;t < map.length;++t){
            let node = getNode(t, k - 1);
            if(node){
                tmpArr.push(node);
            }
        }
        for(let s = 0; s < tmpArr.length;++s){
            let cur = tmpArr[s];
            cur.down = (s + 1 >= tmpArr.length)?tmpArr[0]:tmpArr[s + 1];
            cur.up = (s - 1 < 0)?tmpArr[tmpArr.length-1]:tmpArr[s-1];
        }
    }

    console.log(`-----定义完毕:`);
    // right
    // let cur = head;
    // while (cur.right !== head){
    //     console.log(JSON.stringify(cur));
    //     cur = cur.right;
    // }

    // left
    // let cur = head.left;
    // while (cur.left !== head){
    //     console.log(JSON.stringify(cur));
    //     cur = cur.left;
    // }

    // c1


    // 检查构建的是否正确
    // checkRow(head);

    return head;
}

function checkRow(head){

    let cur = head;
    let cols = [];  //  表示 c1-c7
    while (cur.right !== head){
        // console.log(JSON.stringify(cur));
        cur = cur.right;
        cols.push(cur);
    }
    cols.push(cur);

    // console.log(`cols:${JSON.stringify(cols)}`);

    // 检查各行各列
    // 先检查列
    let c1 = cols[0];
    cur = c1;
    while (cur.down !== c1){
        console.log(JSON.stringify(cur));
        cur = cur.down;
    }
    console.log(JSON.stringify(cur));
}


function step_1(head){
    // // 2.
    if(head.right !== head){
        let c = head.right;

        let cols = [];
        let cur = c.down;
        while (cur !== c){
            cols.push(cur);
            cur = cur.down;
        }

        if(cols.length < 1){
            return;
        }

        // 选择一个未处理的
        let selNode = cols[0];
        let selIdx = selNode.rowIdx;
        selectedRows.push(selIdx);

        let rows = [selNode];
        cur = selNode.right;
        while (cur !== selNode){
            rows.push(cur);
            cur = cur.right;
        }
        console.log(`rows:${JSON.stringify(rows)}`);

        // 简化map


    }
}



let selectedRows = [];
// let usedRows = [];

// 1. 构建
let head = builFramMap();
step_1(head);




